{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find All Possible Recipes from Given Supplies"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph #topological-sort #array #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图 #拓扑排序 #数组 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findAllRecipes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #从给定原材料中找到所有可以做出的菜"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你有 <code>n</code>&nbsp;道不同菜的信息。给你一个字符串数组&nbsp;<code>recipes</code>&nbsp;和一个二维字符串数组&nbsp;<code>ingredients</code>&nbsp;。第&nbsp;<code>i</code>&nbsp;道菜的名字为&nbsp;<code>recipes[i]</code>&nbsp;，如果你有它&nbsp;<strong>所有</strong>&nbsp;的原材料&nbsp;<code>ingredients[i]</code>&nbsp;，那么你可以&nbsp;<strong>做出</strong>&nbsp;这道菜。一道菜的原材料可能是&nbsp;<strong>另一道</strong>&nbsp;菜，也就是说&nbsp;<code>ingredients[i]</code>&nbsp;可能包含&nbsp;<code>recipes</code>&nbsp;中另一个字符串。</p>\n",
    "\n",
    "<p>同时给你一个字符串数组&nbsp;<code>supplies</code>&nbsp;，它包含你初始时拥有的所有原材料，每一种原材料你都有无限多。</p>\n",
    "\n",
    "<p>请你返回你可以做出的所有菜。你可以以 <strong>任意顺序</strong>&nbsp;返回它们。</p>\n",
    "\n",
    "<p>注意两道菜在它们的原材料中可能互相包含。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>recipes = [\"bread\"], ingredients = [[\"yeast\",\"flour\"]], supplies = [\"yeast\",\"flour\",\"corn\"]\n",
    "<b>输出：</b>[\"bread\"]\n",
    "<strong>解释：</strong>\n",
    "我们可以做出 \"bread\" ，因为我们有原材料 \"yeast\" 和 \"flour\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>recipes = [\"bread\",\"sandwich\"], ingredients = [[\"yeast\",\"flour\"],[\"bread\",\"meat\"]], supplies = [\"yeast\",\"flour\",\"meat\"]\n",
    "<b>输出：</b>[\"bread\",\"sandwich\"]\n",
    "<strong>解释：</strong>\n",
    "我们可以做出 \"bread\" ，因为我们有原材料 \"yeast\" 和 \"flour\" 。\n",
    "我们可以做出 \"sandwich\" ，因为我们有原材料 \"meat\" 且可以做出原材料 \"bread\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>recipes = [\"bread\",\"sandwich\",\"burger\"], ingredients = [[\"yeast\",\"flour\"],[\"bread\",\"meat\"],[\"sandwich\",\"meat\",\"bread\"]], supplies = [\"yeast\",\"flour\",\"meat\"]\n",
    "<b>输出：</b>[\"bread\",\"sandwich\",\"burger\"]\n",
    "<strong>解释：</strong>\n",
    "我们可以做出 \"bread\" ，因为我们有原材料 \"yeast\" 和 \"flour\" 。\n",
    "我们可以做出 \"sandwich\" ，因为我们有原材料 \"meat\" 且可以做出原材料 \"bread\" 。\n",
    "我们可以做出 \"burger\" ，因为我们有原材料 \"meat\" 且可以做出原材料 \"bread\" 和 \"sandwich\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>recipes = [\"bread\"], ingredients = [[\"yeast\",\"flour\"]], supplies = [\"yeast\"]\n",
    "<b>输出：</b>[]\n",
    "<strong>解释：</strong>\n",
    "我们没法做出任何菜，因为我们只有原材料 \"yeast\" 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == recipes.length == ingredients.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= ingredients[i].length, supplies.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= recipes[i].length, ingredients[i][j].length, supplies[k].length &lt;= 10</code></li>\n",
    "\t<li><code>recipes[i], ingredients[i][j]</code>&nbsp;和&nbsp;<code>supplies[k]</code>&nbsp;只包含小写英文字母。</li>\n",
    "\t<li>所有&nbsp;<code>recipes</code> 和&nbsp;<code>supplies</code>&nbsp;中的值互不相同。</li>\n",
    "\t<li><code>ingredients[i]</code>&nbsp;中的字符串互不相同。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-all-possible-recipes-from-given-supplies](https://leetcode.cn/problems/find-all-possible-recipes-from-given-supplies/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-all-possible-recipes-from-given-supplies](https://leetcode.cn/problems/find-all-possible-recipes-from-given-supplies/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"bread\"]\\n[[\"yeast\",\"flour\"]]\\n[\"yeast\",\"flour\",\"corn\"]', '[\"bread\",\"sandwich\"]\\n[[\"yeast\",\"flour\"],[\"bread\",\"meat\"]]\\n[\"yeast\",\"flour\",\"meat\"]', '[\"bread\",\"sandwich\",\"burger\"]\\n[[\"yeast\",\"flour\"],[\"bread\",\"meat\"],[\"sandwich\",\"meat\",\"bread\"]]\\n[\"yeast\",\"flour\",\"meat\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        neighbors = {}    # ingredient -> recipes\n",
    "        inDegree = {}\n",
    "        for idx in range(len(recipes)):\n",
    "            curRecipe = recipes[idx]\n",
    "            inDegree[curRecipe] = len(ingredients[idx])\n",
    "            for ingredient in ingredients[idx]:\n",
    "                if ingredient not in neighbors:\n",
    "                    neighbors[ingredient] = []\n",
    "                neighbors[ingredient].append(curRecipe)\n",
    "        \n",
    "        queue = supplies\n",
    "        results = []\n",
    "        recipesSet = set(recipes)\n",
    "        while queue:\n",
    "            curIngredient = queue.pop()\n",
    "            if curIngredient in recipesSet:\n",
    "                results.append(curIngredient)\n",
    "            if curIngredient in neighbors:\n",
    "                for neighbor in neighbors[curIngredient]:\n",
    "                    inDegree[neighbor] -= 1\n",
    "                    if inDegree[neighbor] == 0:\n",
    "                        queue.append(neighbor)\n",
    "        \n",
    "        return results\n",
    "\n",
    "\n",
    "'''\n",
    "topology sort\n",
    "\n",
    "'''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        supplies = set(supplies)\n",
    "        degrees = collections.defaultdict(int)\n",
    "        materialFor = {}\n",
    "        for i in range(len(recipes)):\n",
    "            materials = ingredients[i]\n",
    "            for mat in materials:\n",
    "                if mat not in supplies:\n",
    "                    degrees[i] += 1\n",
    "                    if mat not in materialFor:\n",
    "                        materialFor[mat] = []\n",
    "                    materialFor[mat].append(i)\n",
    "\n",
    "        product = [i for i in range(len(recipes)) if degrees[i] == 0]\n",
    "        ans = []\n",
    "        # print(product, degrees, materialFor)\n",
    "        while product:\n",
    "            index = product.pop()\n",
    "            toMake = recipes[index]\n",
    "            ingredient = ingredients[index]\n",
    "            canMake = True\n",
    "            for mat in ingredient:\n",
    "                if mat not in supplies:\n",
    "                    canMake = False\n",
    "                    break\n",
    "            # print(index, toMake, canMake, ingredient, supplies)\n",
    "            if canMake:\n",
    "                ans.append(toMake)\n",
    "                supplies.add(toMake)\n",
    "                if toMake in materialFor:\n",
    "                    for target in materialFor[toMake]:\n",
    "                        degrees[target] -= 1\n",
    "                        if degrees[target] == 0:\n",
    "                            product.append(target)\n",
    "\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        successors = defaultdict(lambda: [])\n",
    "        indeg = {}\n",
    "        for idx, recipe in enumerate(recipes):\n",
    "            for ii in ingredients[idx]:\n",
    "                successors[ii].append(recipe)\n",
    "            indeg[recipe] = len(ingredients[idx])\n",
    "\n",
    "        ans = []\n",
    "        q = deque(supplies)\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                current = q.popleft()\n",
    "                for s in successors[current]:\n",
    "                    indeg[s] -= 1\n",
    "                    if indeg[s] == 0:\n",
    "                        ans.append(s)\n",
    "                        q.append(s)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        Res = set()\n",
    "        S = set(supplies)\n",
    "        for x in range(105):\n",
    "            for r,i in zip(recipes,ingredients):\n",
    "                f = 1\n",
    "                for a in i:\n",
    "                    if a not in S:\n",
    "                        f = 0;break\n",
    "\n",
    "                if f:\n",
    "                    Res.add(r)\n",
    "                    S.add(r)\n",
    "        return list(Res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        ans, supplies, dct = [], set(supplies), dict(zip(recipes, map(set, ingredients)))\n",
    "        while True:\n",
    "            dct_ = dct.copy()\n",
    "            for recipe, ingredient in dct.items():\n",
    "                if ingredient.issubset(supplies):\n",
    "                    ans.append(recipe)\n",
    "                    supplies.add(recipe)                    \n",
    "                    dct_.pop(recipe)\n",
    "            if len(dct) == len(dct_): return ans\n",
    "            dct = dct_\n",
    "        \n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "    \n",
    "        ans = []\n",
    "        supplies = set(supplies)\n",
    "        dct = dict(zip(recipes, map(set, ingredients)))\n",
    "\n",
    "        while True: \n",
    "            dct_ = dct.copy()\n",
    "\n",
    "            for recipe, ingredient in dct.items():\n",
    "                if ingredient.issubset(supplies):\n",
    "                    ans.append(recipe)\n",
    "                    supplies.add(recipe)\n",
    "                    dct_.pop(recipe)\n",
    "\n",
    "            if len(dct_) == len(dct):\n",
    "                return ans\n",
    "            \n",
    "            dct = dct_\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        ingredients = [set(ingredient) for ingredient in ingredients]\n",
    "        supplies = set(supplies)\n",
    "        results = []\n",
    "\n",
    "        while True:\n",
    "            valid = False\n",
    "            for index, recipe in enumerate(recipes):\n",
    "                if recipe in supplies:\n",
    "                    continue\n",
    "                ingredient = ingredients[index]\n",
    "                if len(ingredient - supplies) == 0:\n",
    "                    supplies.add(recipe)\n",
    "                    results.append(recipe)\n",
    "                    valid = True\n",
    "            if not valid:\n",
    "                break\n",
    "        \n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        supp = set(supplies)\n",
    "        ingredient = [set(i) for i in ingredients]\n",
    "        result = []\n",
    "        added = True\n",
    "        while added:\n",
    "            added = False\n",
    "            for rec, ing in zip(recipes, ingredient):\n",
    "                if rec not in supp and ing <= supp:\n",
    "                    added = True\n",
    "                    supp.add(rec)\n",
    "                    result.append(rec)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        supplies = set(supplies)\n",
    "        cancook = set()\n",
    "        for _ in range(len(recipes)):\n",
    "            for recipe, ingredient in zip(recipes, ingredients):\n",
    "                if recipe in cancook:\n",
    "                    continue\n",
    "                s = True\n",
    "                for food in ingredient:\n",
    "                    if food not in supplies:\n",
    "                        s = False\n",
    "                        break\n",
    "                if s:\n",
    "                    supplies.add(recipe)\n",
    "                    cancook.add(recipe)\n",
    "        \n",
    "        return list(cancook)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ini: List[List[str]], sup: List[str]) -> List[str]:\n",
    "        e=Counter(sup)\n",
    "        def g(l,r):\n",
    "            for x in l.items():\n",
    "               if x[0] in r:\n",
    "                  continue\n",
    "               else:\n",
    "                  return False\n",
    "            return True\n",
    "        ans=[]    \n",
    "        v=Counter()\n",
    "        while 1 :\n",
    "         m=len(e)   \n",
    "         for i in range(len(recipes)):\n",
    "            c=Counter(ini[i])\n",
    "            if g(c,e):\n",
    "                if recipes[i] not in v:\n",
    "                 ans.append(recipes[i])\n",
    "                v[recipes[i]]+=1\n",
    "                \n",
    "                e[recipes[i]]+=1\n",
    "         if m==len(e):\n",
    "             break       \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        sup_dic = set(supplies)\n",
    "        res = []\n",
    "        remain_recipe = set(recipes)\n",
    "        while True:\n",
    "            new_add_flag = 0\n",
    "            for i in range(len(recipes)):\n",
    "                if recipes[i]  not in remain_recipe:   #这道菜之前已经被做出来了\n",
    "                    continue\n",
    "                can_make_flag = 1\n",
    "                for tmp_mat in ingredients[i]:\n",
    "                    if tmp_mat in sup_dic:\n",
    "                        continue\n",
    "                    else:\n",
    "                        can_make_flag = 0\n",
    "                        break\n",
    "                if can_make_flag == 1:\n",
    "                    sup_dic.add( recipes[i] )\n",
    "                    res.append( recipes[i] )\n",
    "                    remain_recipe.remove( recipes[i] )\n",
    "                    new_add_flag = 1\n",
    "            if new_add_flag == 0:\n",
    "                break\n",
    "            else:\n",
    "                continue\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "\n",
    "        '''\n",
    "        sr = set()\n",
    "        ss = set()\n",
    "        '''\n",
    "\n",
    "        ss = set(supplies)\n",
    "        l1 = len(recipes)\n",
    "        adj = {r: set() for r in recipes}\n",
    "        degree = [0] * l1\n",
    "        q = deque() \n",
    "        for idx, r in enumerate(recipes):\n",
    "            for ing in ingredients[idx]:\n",
    "                if ing not in ss:\n",
    "                    degree[idx] += 1\n",
    "                if ing in adj:\n",
    "                    adj[ing].add(idx)\n",
    "        \n",
    "        for i, d in enumerate(degree):\n",
    "            if d == 0:\n",
    "                q.append(i)\n",
    "\n",
    "        ans = []\n",
    "        while q:\n",
    "            cur = q.pop()\n",
    "            ans.append(recipes[cur])\n",
    "            for nxt in adj[recipes[cur]]:\n",
    "                degree[nxt] -= 1\n",
    "                if degree[nxt] == 0:\n",
    "                    q.append(nxt)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "    \n",
    "        ans = []\n",
    "        supplies = set(supplies)\n",
    "        dct = dict(zip(recipes, map(set, ingredients)))\n",
    "\n",
    "        while True: \n",
    "            dct_ = dct.copy()\n",
    "\n",
    "            for recipe, ingredient in dct.items():\n",
    "                if ingredient.issubset(supplies):\n",
    "                    ans.append(recipe)\n",
    "                    supplies.add(recipe)\n",
    "                    dct_.pop(recipe)\n",
    "\n",
    "            if len(dct_) == len(dct):\n",
    "                return ans\n",
    "            \n",
    "            dct = dct_\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "\n",
    "        graph = defaultdict(list)\n",
    "        in_degree = defaultdict(int)\n",
    "\n",
    "        n = len(recipes)\n",
    "\n",
    "        for s in supplies:\n",
    "            in_degree[s] = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            for s in ingredients[i]:\n",
    "                graph[s].append(recipes[i])\n",
    "                in_degree[recipes[i]]+=1\n",
    "        \n",
    "        q = []\n",
    "\n",
    "        for k in in_degree.keys():\n",
    "            if in_degree[k] == 0:\n",
    "                in_degree[k] = -1\n",
    "                q.append(k)\n",
    "        \n",
    "        res = []\n",
    "\n",
    "        while len(q):\n",
    "            cur_s = q[-1]\n",
    "            q.pop()\n",
    "            if cur_s in recipes:\n",
    "                res.append(cur_s)\n",
    "\n",
    "            for to_s in graph[cur_s]:\n",
    "                in_degree[to_s] -=1\n",
    "                if in_degree[to_s] == 0:\n",
    "                    in_degree[to_s] = -1\n",
    "                    q.append(to_s)\n",
    "                \n",
    "        return res\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        res_set = set()\n",
    "        g = defaultdict(list)\n",
    "        in_degress = defaultdict(int)\n",
    "        name2idx = dict()\n",
    "        idx = 0\n",
    "        for i in range(len(recipes)):\n",
    "            r = recipes[i]\n",
    "            if not r in name2idx:\n",
    "                name2idx[r] = idx\n",
    "                idx+=1\n",
    "            for ing in ingredients[i]:\n",
    "                if not ing in name2idx:\n",
    "                    name2idx[ing] = idx\n",
    "                    idx+=1\n",
    "                g[name2idx[ing]].append(name2idx[r])\n",
    "                in_degress[name2idx[r]] += 1\n",
    "\n",
    "        idx2name = {v:k for k,v in name2idx.items()}\n",
    "        in_degress = [in_degress[i] if i in in_degress else 0 for i in range(idx)]\n",
    "        q = []\n",
    "        for i in range(idx):\n",
    "            if in_degress[i] == 0:\n",
    "                if idx2name[i] not in supplies:\n",
    "                    in_degress[i] = float('inf')\n",
    "                else:\n",
    "                    q.append(i)\n",
    "        while q:\n",
    "            x = q[0]\n",
    "            res_set.add(x)\n",
    "            q.pop(0)\n",
    "            for y in g[x]:\n",
    "                in_degress[y] -= 1\n",
    "                if in_degress[y] == 0:\n",
    "                    q.append(y)\n",
    "\n",
    "        res = []\n",
    "        for r in recipes:\n",
    "            if name2idx[r] in res_set:\n",
    "                res.append(r)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        supplies = set(supplies)\n",
    "        n = len(recipes)\n",
    "        vst = [0] * n\n",
    "        while True:\n",
    "            flag = 0\n",
    "            for i in range(n):\n",
    "                if vst[i]:\n",
    "                    continue\n",
    "                ing = ingredients[i]\n",
    "                for one in ing:\n",
    "                    if one not in supplies:\n",
    "                        break\n",
    "                else:\n",
    "                    supplies.add(recipes[i])\n",
    "                    vst[i] = 1\n",
    "                    flag = 1\n",
    "            if not flag:\n",
    "                return [recipes[i] for i in range(n) if vst[i]]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        ans = set()\n",
    "        graph = defaultdict(list)\n",
    "        in_degree = defaultdict(int)\n",
    "        for i, ingredient in enumerate(ingredients):\n",
    "            all_in_supplies = True\n",
    "            for supply in ingredient:\n",
    "                if supply not in supplies:\n",
    "                    all_in_supplies = False\n",
    "                    graph[supply].append(recipes[i])\n",
    "                    in_degree[recipes[i]] += 1\n",
    "            if all_in_supplies: ans.add(recipes[i])\n",
    "        dq = deque()\n",
    "        dq.extend(ans)\n",
    "        while dq:\n",
    "            node = dq.popleft()\n",
    "            if node not in ans: ans.add(node)\n",
    "            for to_node in graph[node]:\n",
    "                in_degree[to_node] -= 1\n",
    "                if in_degree[to_node] == 0:\n",
    "                    dq.append(to_node)\n",
    "        return list(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "            \n",
    "        g = defaultdict(list)\n",
    "        deg = {}\n",
    "        for r, ing in zip(recipes, ingredients):\n",
    "            for s in ing:\n",
    "                g[s].append(r)  # 从这道菜的原材料向这道菜连边\n",
    "            deg[r] = len(ing)\n",
    "        ans = []\n",
    "        q = deque(supplies)  # 拓扑排序（用初始原材料当队列）\n",
    "        while q:\n",
    "            for r in g[q.popleft()]:\n",
    "                deg[r] -= 1\n",
    "                if deg[r] == 0:  # 这道菜的所有原材料我们都有\n",
    "                    q.append(r)\n",
    "                    ans.append(r)\n",
    "        return ans\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/find-all-possible-recipes-from-given-supplies/solutions/1176904/go-tuo-bu-pai-xu-by-endlesscheng-lnlg/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        n = len(recipes)\n",
    "        # 图\n",
    "        depend = defaultdict(list)\n",
    "        # 入度统计\n",
    "        cnt = Counter()\n",
    "        for i in range(n):\n",
    "            for ing in ingredients[i]:\n",
    "                depend[ing].append(recipes[i])\n",
    "            cnt[recipes[i]] = len(ingredients[i])\n",
    "        \n",
    "        ans = []\n",
    "        # 把初始的原材料放入队列\n",
    "        q = deque(supplies)\n",
    "        \n",
    "        # 拓扑排序\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            if cur in depend:\n",
    "                for rec in depend[cur]:\n",
    "                    cnt[rec] -= 1\n",
    "                    # 如果入度变为 0，说明可以做出这道菜\n",
    "                    if cnt[rec] == 0:\n",
    "                        ans.append(rec)\n",
    "                        q.append(rec)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        ingtorec = defaultdict(list)\n",
    "        degree = {}\n",
    "        for i in range(len(recipes)):\n",
    "            rec = recipes[i]\n",
    "            ing = ingredients[i]\n",
    "            degree[rec] = len(ing)\n",
    "            for j in ing:\n",
    "                ingtorec[j].append(rec)\n",
    "\n",
    "        i = 0\n",
    "        result = []\n",
    "        while i < len(supplies):\n",
    "            sup = supplies[i]\n",
    "            if sup in ingtorec:\n",
    "                recs = ingtorec[sup]\n",
    "                for rec in recs:\n",
    "                    degree[rec] -= 1\n",
    "                    if degree[rec] == 0:\n",
    "                        result.append(rec)\n",
    "                        if rec in ingtorec:\n",
    "                            supplies.append(rec)\n",
    "            i += 1\n",
    "            \n",
    "        return result    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Vertex:\n",
    "    def __init__(self):\n",
    "        self.indegree = 0\n",
    "        self.nexts = set()\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        data = self.construct_graph(recipes, ingredients)\n",
    "        q, result, valid_set = deque(), [], set(recipes)\n",
    "        for supply in supplies:\n",
    "            if supply in data:\n",
    "                q.append(supply)\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            if cur in valid_set:\n",
    "                result.append(cur)\n",
    "            cur_vertex = data[cur]\n",
    "            for nxt in cur_vertex.nexts:\n",
    "                data[nxt].indegree -= 1\n",
    "                if data[nxt].indegree == 0:\n",
    "                    q.append(nxt)\n",
    "        return result\n",
    "\n",
    "    def construct_graph(self, recipes, ingredients):\n",
    "        result = {}\n",
    "        for i, cur in enumerate(recipes):\n",
    "            prevs = ingredients[i]\n",
    "            if cur not in result:\n",
    "                result[cur] = Vertex()\n",
    "            for prev in prevs:\n",
    "                if prev not in result:\n",
    "                    result[prev] = Vertex()\n",
    "                result[prev].nexts.add(cur)\n",
    "                result[cur].indegree += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    from collections import defaultdict, Counter\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        n = len(recipes)\n",
    "        depend = defaultdict(list)\n",
    "        ans = []\n",
    "        cnt = Counter()\n",
    "        for i in range(n):\n",
    "            for ing in ingredients[i]:\n",
    "                depend[ing].append(recipes[i])\n",
    "            cnt[recipes[i]] = len(ingredients[i])\n",
    "        q = deque(supplies)\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            if cur in depend:\n",
    "                for rec in depend[cur]:\n",
    "                    cnt[rec] -= 1\n",
    "                    if cnt[rec] == 0:\n",
    "                        ans.append(rec)\n",
    "                        q.append(rec)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "      indegree = collections.defaultdict(int)\n",
    "      tree = collections.defaultdict(list)\n",
    "      for dish, source in zip(recipes, ingredients):\n",
    "        for i in source:\n",
    "          tree[i].append(dish)\n",
    "          indegree[dish] += 1\n",
    "\n",
    "      ans = []\n",
    "      while supplies:\n",
    "        tmp = []\n",
    "        for cur in supplies:\n",
    "          for nex in tree[cur]:\n",
    "            indegree[nex] -= 1\n",
    "            if indegree[nex] == 0:\n",
    "              ans.append(nex)\n",
    "              tmp.append(nex)\n",
    "        supplies = tmp\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        g = defaultdict(list)\n",
    "        deg = {}\n",
    "        for r, ing in zip(recipes, ingredients):\n",
    "            for s in ing:\n",
    "                g[s].append(r)  # 从这道菜的原材料向这道菜连边\n",
    "            deg[r] = len(ing)\n",
    "        ans = []\n",
    "        q = deque(supplies)  # 拓扑排序（用初始原材料当队列）\n",
    "        while q:\n",
    "            for r in g[q.popleft()]:\n",
    "                deg[r] -= 1\n",
    "                if deg[r] == 0:  # 这道菜的所有原材料我们都有\n",
    "                    q.append(r)\n",
    "                    ans.append(r)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        # 1. build adjacency list and indegree list for digraph, edge: ingredient -> recipe\n",
    "        g = defaultdict(list)\n",
    "        indegree = defaultdict(int)\n",
    "        for recipe, ingredient in zip(recipes, ingredients):\n",
    "            for i in ingredient:\n",
    "                g[i].append(recipe)\n",
    "            indegree[recipe] = len(ingredient)\n",
    "        \n",
    "\n",
    "        # 2. BFS topological sort\n",
    "        ans = []\n",
    "        queue = deque(supplies)\n",
    "        while queue:\n",
    "            supply = queue.popleft()\n",
    "            for recipe in g[supply]:\n",
    "                indegree[recipe] -= 1\n",
    "                # we have all the ingredients needed for the recipe\n",
    "                if indegree[recipe] == 0:\n",
    "                    queue.append(recipe)\n",
    "                    ans.append(recipe)\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        nodes = set(recipes+supplies)\n",
    "        degree = defaultdict(int)\n",
    "        dct = defaultdict(list)\n",
    "        n = len(recipes)\n",
    "        for i in range(n):\n",
    "            degree[recipes[i]] = len(ingredients[i])\n",
    "            for p in ingredients[i]:\n",
    "                dct[p].append(recipes[i])\n",
    "            nodes = nodes.union(set(ingredients[i]))\n",
    "        \n",
    "        exist = set(supplies)\n",
    "        for s in nodes:\n",
    "            if s in exist:\n",
    "                degree[s] = 0\n",
    "            elif not degree[s]:\n",
    "                degree[s] = 1\n",
    "    \n",
    "        stack = [i for i in nodes if not degree[i]]\n",
    "        visit = set(stack)\n",
    "        while stack:\n",
    "            nex = []\n",
    "            for x in stack:\n",
    "                for y in dct[x]:\n",
    "                    degree[y] -= 1\n",
    "                    if not degree[y]:\n",
    "                        nex.append(y)\n",
    "                        visit.add(y)\n",
    "            stack = nex[:]\n",
    "        return [x for x in recipes if x in visit]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        n = len(recipes)\n",
    "        depend = defaultdict(list)\n",
    "        cnt = Counter()\n",
    "        for i in range(n):\n",
    "            for ing in ingredients[i]:\n",
    "                depend[ing].append(recipes[i])\n",
    "            cnt[recipes[i]] = len(ingredients[i])\n",
    "        ans = list()\n",
    "        q = deque(supplies)\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            if cur in depend:\n",
    "                for rec in depend[cur]:\n",
    "                    cnt[rec] -= 1\n",
    "                    if cnt[rec] == 0:\n",
    "                        ans.append(rec)\n",
    "                        q.append(rec)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        graph = defaultdict(list)\n",
    "        indegree = defaultdict(int)\n",
    "        \n",
    "        for i in range(len(recipes)):\n",
    "            for ingredient in ingredients[i]:\n",
    "                graph[ingredient].append(recipes[i])\n",
    "            indegree[recipes[i]] += len(ingredients[i])\n",
    "        \n",
    "        queue = deque(supplies)\n",
    "        res = []\n",
    "\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            for next_node in graph[node]:\n",
    "                indegree[next_node] -= 1\n",
    "                if indegree[next_node] == 0:\n",
    "                    res.append(next_node)\n",
    "                    queue.append(next_node)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        # 拓扑排序\n",
    "\n",
    "        g = defaultdict(list) # 获取每个原料：能做的菜\n",
    "        d = {} # 每道菜：需要原料数目\n",
    "        for r, ing in zip(recipes, ingredients):\n",
    "            for s in ing:\n",
    "                g[s].append(r) # 将菜与原材料连边\n",
    "            d[r] = len(ing)\n",
    "        ans = []\n",
    "        q = deque(supplies) # 当下拥有的原料\n",
    "        while q:\n",
    "            for r in g[q.popleft()]:\n",
    "                d[r] -= 1\n",
    "                if d[r] == 0: # 这道菜所有原材料都有\n",
    "                    q.append(r) # 因为存在菜品也是原材料\n",
    "                    ans.append(r)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        n = len(recipes)\n",
    "        graph = collections.defaultdict(list)\n",
    "        indegrees = collections.defaultdict(int)\n",
    "        for i in range(n):\n",
    "            for ingredient in ingredients[i]:\n",
    "                graph[ingredient].append(recipes[i])\n",
    "            indegrees[recipes[i]] = len(ingredients[i])\n",
    "        res = []\n",
    "        q = deque(supplies)\n",
    "        while q:\n",
    "            x = q.popleft()\n",
    "            if x in graph:\n",
    "                for recipe in graph[x]:\n",
    "                    indegrees[recipe] -= 1\n",
    "                    if indegrees[recipe] == 0:\n",
    "                        res.append(recipe)\n",
    "                        q.append(recipe)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        g = defaultdict(list)\n",
    "        deg = {}\n",
    "        for r, ing in zip(recipes, ingredients):\n",
    "            for s in ing:\n",
    "                g[s].append(r)  # 从这道菜的原材料向这道菜连边\n",
    "            deg[r] = len(ing)\n",
    "        ans = []\n",
    "        q = deque(supplies)  # 拓扑排序（用初始原材料当队列）\n",
    "        while q:\n",
    "            for r in g[q.popleft()]:\n",
    "                deg[r] -= 1\n",
    "                if deg[r] == 0:  # 这道菜的所有原材料我们都有\n",
    "                    q.append(r)\n",
    "                    ans.append(r)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "\n",
    "        g = defaultdict(list)\n",
    "        deg = {}\n",
    "\n",
    "        for r, ing in zip(recipes, ingredients):\n",
    "            for s in ing:\n",
    "                g[s].append(r)\n",
    "            deg[r] = len(ing)\n",
    "        \n",
    "        ans = []\n",
    "        q = deque(supplies)\n",
    "        while q:\n",
    "            for r in g[q.popleft()]:\n",
    "                deg[r] -= 1\n",
    "                if deg[r] == 0:\n",
    "                    q.append(r)\n",
    "                    ans.append(r)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        ruDu = dict()\n",
    "        yuanLiao = deque(supplies)\n",
    "        jieDianJiLu = defaultdict(list)\n",
    "        res = list()\n",
    "        for i in range(len(recipes)):\n",
    "            ruDu[recipes[i]] = len(ingredients[i])\n",
    "            for  j in ingredients[i]:\n",
    "                jieDianJiLu[j].append(recipes[i])\n",
    "        \n",
    "        while len(yuanLiao)!=0:\n",
    "            caiLiao = yuanLiao.popleft()\n",
    "            for i in jieDianJiLu[caiLiao]:\n",
    "                ruDu[i] -=1\n",
    "                if ruDu[i] == 0:\n",
    "                    yuanLiao.append(i)\n",
    "                    res.append(i)\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        n = len(recipes)\n",
    "        # 图\n",
    "        depend = defaultdict(list)\n",
    "        # 入度统计\n",
    "        cnt = Counter()\n",
    "        for i in range(n):\n",
    "            for ing in ingredients[i]:\n",
    "                depend[ing].append(recipes[i])\n",
    "            cnt[recipes[i]] = len(ingredients[i])\n",
    "        \n",
    "        ans = list()\n",
    "        # 把初始的原材料放入队列\n",
    "        q = deque(supplies)\n",
    "        \n",
    "        # 拓扑排序\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            if cur in depend:\n",
    "                for rec in depend[cur]:\n",
    "                    cnt[rec] -= 1\n",
    "                    # 如果入度变为 0，说明可以做出这道菜\n",
    "                    if cnt[rec] == 0:\n",
    "                        ans.append(rec)\n",
    "                        q.append(rec)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "\n",
    "        g = defaultdict(list)\n",
    "\n",
    "        deg = {}\n",
    "\n",
    "        for r, ing in zip(recipes, ingredients):\n",
    "\n",
    "            for s in ing:\n",
    "\n",
    "                g[s].append(r)  # 从这道菜的原材料向这道菜连边\n",
    "\n",
    "            deg[r] = len(ing)\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        q = deque(supplies)  # 拓扑排序（用初始原材料当队列）\n",
    "\n",
    "        while q:\n",
    "\n",
    "            for r in g[q.popleft()]:\n",
    "\n",
    "                deg[r] -= 1\n",
    "\n",
    "                if deg[r] == 0:  # 这道菜的所有原材料我们都有\n",
    "\n",
    "                    q.append(r)\n",
    "\n",
    "                    ans.append(r)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        n = len(recipes)\n",
    "        # 图\n",
    "        depend = defaultdict(list)\n",
    "        # 入度统计\n",
    "        cnt = Counter()\n",
    "        for i in range(n):\n",
    "            for ing in ingredients[i]:\n",
    "                depend[ing].append(recipes[i])\n",
    "            cnt[recipes[i]] = len(ingredients[i])\n",
    "        \n",
    "        ans = list()\n",
    "        # 把初始的原材料放入队列\n",
    "        q = deque(supplies)\n",
    "        \n",
    "        # 拓扑排序\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            if cur in depend:\n",
    "                for rec in depend[cur]:\n",
    "                    cnt[rec] -= 1\n",
    "                    # 如果入度变为 0，说明可以做出这道菜\n",
    "                    if cnt[rec] == 0:\n",
    "                        ans.append(rec)\n",
    "                        q.append(rec)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\r\n",
    "        g = defaultdict(list)\r\n",
    "        deg = {}\r\n",
    "        for r, ing in zip(recipes, ingredients):\r\n",
    "            for s in ing:\r\n",
    "                g[s].append(r)  # 从这道菜的原材料向这道菜连边\r\n",
    "            deg[r] = len(ing)\r\n",
    "        ans = []\r\n",
    "        q = deque(supplies)  # 拓扑排序（用初始原材料当队列）\r\n",
    "        while q:\r\n",
    "            for r in g[q.popleft()]:\r\n",
    "                deg[r] -= 1\r\n",
    "                if deg[r] == 0:  # 这道菜的所有原材料我们都有\r\n",
    "                    q.append(r)\r\n",
    "                    ans.append(r)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        from collections import defaultdict\n",
    "        from collections import Counter\n",
    "        n, res =len(recipes), []\n",
    "        cnt = Counter()\n",
    "        dep = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            cnt[recipes[i]] = len(ingredients[i])\n",
    "            for d in ingredients[i]:\n",
    "                dep[d].append(recipes[i])\n",
    "        q= deque(supplies)\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            for i in dep[cur]:\n",
    "                cnt[i] = cnt[i]-1\n",
    "                if cnt[i]==0:\n",
    "                    res.append(i)\n",
    "                    q.append(i)\n",
    "        return res\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        n = len(recipes)\n",
    "        # 图\n",
    "        neighbors = defaultdict(list)\n",
    "        # 入度统计\n",
    "        indeg = {}\n",
    "        for i in range(n):\n",
    "            for ing in ingredients[i]:\n",
    "                neighbors[ing].append(recipes[i])\n",
    "            indeg[recipes[i]] = len(ingredients[i])\n",
    "        \n",
    "        ans = list()\n",
    "        # 把初始的原材料放入队列\n",
    "        q = deque(supplies)\n",
    "        \n",
    "        # 拓扑排序\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            if cur in neighbors:\n",
    "                for rec in neighbors[cur]:\n",
    "                    indeg[rec] -= 1\n",
    "                    # 如果入度变为 0，说明可以做出这道菜\n",
    "                    if indeg[rec] == 0:\n",
    "                        ans.append(rec)\n",
    "                        q.append(rec)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        g = defaultdict(list)\n",
    "        deg = {}\n",
    "        for r,ing in zip(recipes,ingredients):\n",
    "            for s in ing:\n",
    "                g[s].append(r)\n",
    "            deg[r]=len(ing)\n",
    "        ans =[]\n",
    "\n",
    "        q =deque(supplies)\n",
    "        while q:\n",
    "            for r in g[q.popleft()]:\n",
    "                deg[r]-=1\n",
    "                if deg[r]==0:\n",
    "                    q.append(r)\n",
    "                    ans.append(r)\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        graph = collections.defaultdict(list)\n",
    "        indeg = collections.defaultdict(int)\n",
    "        for u, vs in zip(recipes, ingredients):\n",
    "            for v in vs:\n",
    "                graph[v].append(u)\n",
    "                indeg[u] += 1\n",
    "\n",
    "        \n",
    "        deque = collections.deque(supplies)\n",
    "\n",
    "        while deque:\n",
    "            curr = deque.popleft()\n",
    "            for nxt in graph[curr]:\n",
    "                indeg[nxt] -= 1\n",
    "                if indeg[nxt] == 0:\n",
    "                    deque.append(nxt)\n",
    "\n",
    "        res = [rec for rec in recipes if indeg[rec] == 0]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        # 用菜-》菜肴\n",
    "        n = len(recipes)\n",
    "        depend = defaultdict(list)\n",
    "        # indegree\n",
    "        cnt = Counter()\n",
    "        for i in range(n): # 统一index\n",
    "            for ing in ingredients[i]:\n",
    "                depend[ing].append(recipes[i])\n",
    "            #记录recipes里每个,对应的需要的ingredient \n",
    "            cnt[recipes[i]] = len(ingredients[i])\n",
    "\n",
    "        ans = list()\n",
    "        q = deque(supplies)\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            if cur in depend:\n",
    "                for follow in depend[cur]:\n",
    "                    cnt[follow] -= 1\n",
    "                    if cnt[follow] == 0:\n",
    "                        ans.append(follow)\n",
    "                        q.append(follow)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        edges=collections.defaultdict(list)\n",
    "        indeg=collections.defaultdict(int)\n",
    "        ans=[]\n",
    "        for i in range(len(recipes)):\n",
    "            for j in range(len(ingredients[i])):\n",
    "                edges[ingredients[i][j]].append(recipes[i])\n",
    "                indeg[recipes[i]]+=1\n",
    "\n",
    "        q=collections.deque(supplies)\n",
    "        while q:\n",
    "            gre=q.popleft()\n",
    "            if gre in edges:\n",
    "                for food in edges[gre]:\n",
    "                    indeg[food]-=1\n",
    "                    if indeg[food]==0:\n",
    "                        q.append(food)\n",
    "                        ans.append(food)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        indeg = defaultdict(int)\n",
    "        graph = defaultdict(list)\n",
    "        for recipe, ingredient in zip(recipes, ingredients):\n",
    "            for ing in ingredient:\n",
    "                graph[ing].append(recipe)\n",
    "                indeg[recipe] += 1\n",
    "        recipes = set(recipes)\n",
    "        # topological sort\n",
    "        q = deque([supply for supply in supplies if indeg[supply] == 0])\n",
    "        res = []\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            if cur in recipes:\n",
    "                res.append(cur)\n",
    "            for nxt in graph[cur]:\n",
    "                indeg[nxt] -= 1\n",
    "                if indeg[nxt] == 0:\n",
    "                    q.append(nxt)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        rec={}\n",
    "        ing={}\n",
    "        ans=[]\n",
    "        for it1,it2 in zip(recipes,ingredients):\n",
    "            for it3 in it2:\n",
    "                rec.setdefault(it3,[]).append(it1)\n",
    "                ing.setdefault(it1,{it3}).add(it3)\n",
    "        \n",
    "        print(rec)\n",
    "        print(ing)\n",
    "        for it1 in supplies:\n",
    "            for it2 in rec.setdefault(it1,[]):\n",
    "                ing[it2].remove(it1)\n",
    "                if len(ing[it2])==0:\n",
    "                    supplies.append(it2)\n",
    "                    ans.append(it2)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        res = set()\n",
    "        sup = set(supplies)\n",
    "        ingredients = [set(x) for x in ingredients]\n",
    "        i = 0\n",
    "        while i < len(recipes):\n",
    "            x = recipes[i]\n",
    "            if x not in res and x not in sup and ingredients[i].issubset(sup) :\n",
    "                sup.add(x)\n",
    "                res.add(x)\n",
    "                i = 0 # 每添加一个都要重新开始\n",
    "            else: i += 1\n",
    "        \n",
    "        return list(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        supplies = set(supplies)\n",
    "        \n",
    "        n = len(recipes)\n",
    "        dict1 = {recipes[i]:set(ingredients[i]) for i in range(n)}\n",
    "        for x in supplies:\n",
    "            dict1[x] = set()\n",
    "\n",
    "        res = []\n",
    "        visited = set()\n",
    "\n",
    "\n",
    "        def dfs(i):\n",
    "            if i not in dict1:\n",
    "                return False\n",
    "            if i in visited:\n",
    "                return False\n",
    "            if len(dict1[i]) == 0:\n",
    "                return True\n",
    "            visited.add(i)\n",
    "            for nxt in dict1[i]:\n",
    "                if not dfs(nxt):\n",
    "                    return False\n",
    "            visited.remove(i)\n",
    "            res.append(i)\n",
    "            dict1[i] = set()\n",
    "            return True\n",
    "        \n",
    "        for x in recipes:\n",
    "            dfs(x)\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        graph = {r: ings for r, ings in zip(recipes, ingredients)}\n",
    "        can_make = {s: True for s in supplies}\n",
    "        \n",
    "        def dfs(r):\n",
    "            if r not in can_make:\n",
    "                can_make[r] = False\n",
    "                if r in graph:\n",
    "                    can_make[r] = all(dfs(ing) for ing in graph[r])\n",
    "            return can_make[r]\n",
    "        return [r for r in recipes if dfs(r)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        graph = dict(zip(recipes, ingredients))\n",
    "        can_make = dict.fromkeys(supplies, True)\n",
    "        \n",
    "        def dfs(r):\n",
    "            if r not in can_make:\n",
    "                can_make[r] = False\n",
    "                if r in graph:\n",
    "                    can_make[r] = all(map(dfs, graph[r]))\n",
    "                    \n",
    "            return can_make[r]\n",
    "        return [*filter(dfs, recipes)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        res = []\n",
    "        memo = set()\n",
    "        v = [0]*len(recipes)\n",
    "        def f(t):\n",
    "            if t in memo:\n",
    "                return True\n",
    "            v[t] = 1\n",
    "            for i in ingredients[t]:\n",
    "                if i not in supplies:\n",
    "                    if i in recipes:\n",
    "                        #print(recipes.index(i))\n",
    "                        if v[recipes.index(i)]==1 or not f(recipes.index(i)):\n",
    "                            return False\n",
    "                    else:\n",
    "                        return False\n",
    "            v[t] = 0\n",
    "            memo.add(t)\n",
    "            return True\n",
    "        for i in range(len(recipes)):\n",
    "            if f(i):\n",
    "                res.append(recipes[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        ingre = dict(zip(recipes, ingredients))\n",
    "        can_make = dict.fromkeys(supplies, True)\n",
    "        \n",
    "        def dfs(r):\n",
    "            if r not in can_make:\n",
    "                can_make[r] = False\n",
    "                if r in ingre:\n",
    "                    can_make[r] = all(map(dfs, ingre[r]))\n",
    "            return can_make[r]\n",
    "            \n",
    "        return [*filter(dfs, recipes)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        graph = dict(zip(recipes, ingredients))\n",
    "        can_make = {s: True for s in supplies}\n",
    "        \n",
    "        def dfs(r):\n",
    "            if r not in can_make:\n",
    "                can_make[r] = False\n",
    "                if r in graph:\n",
    "                    can_make[r] = all(dfs(ing) for ing in graph[r])\n",
    "            return can_make[r]\n",
    "        return [r for r in recipes if dfs(r)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        graph = dict(zip(recipes, ingredients))\n",
    "        can_make = dict.fromkeys(supplies, True)\n",
    "        \n",
    "        def dfs(r):\n",
    "            if r not in can_make:\n",
    "                can_make[r] = False\n",
    "                if r in graph:\n",
    "                    can_make[r] = all(map(dfs, graph[r]))\n",
    "            return can_make[r]\n",
    "            \n",
    "        return [*filter(dfs, recipes)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        recipes_map = {name: i for i, name in enumerate(recipes)}\n",
    "        supplies_set = {x for x in supplies}\n",
    "        \n",
    "        def find(name):\n",
    "            if name in supplies_set:\n",
    "                return True \n",
    "            index = recipes_map.get(name, -1)\n",
    "            if index < 0:\n",
    "                return False \n",
    "            recipes_map[name] = -1\n",
    "            for mate in ingredients[index]:\n",
    "                if not find(mate):\n",
    "                    return False \n",
    "            supplies_set.add(name)\n",
    "            return True \n",
    "\n",
    "        for name in recipes:\n",
    "            if find(name):\n",
    "                ans.append(name)\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        ingre = dict(zip(recipes, ingredients))\n",
    "        can_make = dict.fromkeys(supplies, True)\n",
    "        \n",
    "        def dfs(r):\n",
    "            if r not in can_make:\n",
    "                can_make[r] = False\n",
    "                if r in ingre:\n",
    "                    can_make[r] = all(map(dfs, ingre[r]))\n",
    "            return can_make[r]\n",
    "            \n",
    "        return [*filter(dfs, recipes)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        ingre = dict(zip(recipes, ingredients))\n",
    "        can_make = dict.fromkeys(supplies, True)\n",
    "        \n",
    "        def dfs(r):\n",
    "            if r not in can_make:\n",
    "                can_make[r] = False\n",
    "                if r in ingre:\n",
    "                    can_make[r] = all(map(dfs, ingre[r]))\n",
    "            return can_make[r]\n",
    "            \n",
    "        return [*filter(dfs, recipes)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        graph = dict(zip(recipes, ingredients))\n",
    "        can_make = dict.fromkeys(supplies, True)\n",
    "        \n",
    "        def dfs(r):\n",
    "            if r not in can_make:\n",
    "                can_make[r] = False\n",
    "                if r in graph:\n",
    "                    can_make[r] = all(dfs(ing) for ing in graph[r])\n",
    "            return can_make[r]\n",
    "        return [*filter(dfs, recipes)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        graph = dict(zip(recipes, ingredients))\n",
    "        can_make = dict.fromkeys(supplies, True)\n",
    "        \n",
    "        def dfs(r):\n",
    "            if r not in can_make:\n",
    "                can_make[r] = False\n",
    "                if r in graph:\n",
    "                    can_make[r] = all(dfs(ing) for ing in graph[r])\n",
    "            return can_make[r]\n",
    "        return [r for r in recipes if dfs(r)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        graph = dict(zip(recipes, ingredients))\n",
    "        can_make = dict.fromkeys(supplies, True)\n",
    "        \n",
    "        def dfs(r):\n",
    "            if r not in can_make:\n",
    "                can_make[r] = False\n",
    "                if r in graph:\n",
    "                    can_make[r] = all(dfs(ing) for ing in graph[r])\n",
    "            return can_make[r]\n",
    "        return [r for r in recipes if dfs(r)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "        supplies = set(supplies)\n",
    "\n",
    "        reci = {}\n",
    "\n",
    "        for r, i in zip(recipes, ingredients):\n",
    "            reci[r] = i\n",
    "        \n",
    "        def check(x, depth):\n",
    "            if x in ret:\n",
    "                return True\n",
    "            \n",
    "            if depth > 200:\n",
    "                return False\n",
    "\n",
    "            if x in supplies:\n",
    "                return True\n",
    "\n",
    "            if x in reci:\n",
    "                for y in reci[x]:\n",
    "                    if not check(y, depth + 1):\n",
    "                        return False\n",
    "\n",
    "                return True\n",
    "\n",
    "            return False\n",
    "\n",
    "        ret = set()\n",
    "\n",
    "        for r in recipes:\n",
    "            if check(r, 0):\n",
    "                ret.add(r)\n",
    "\n",
    "        return list(ret)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
